#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

void flatten(TreeNode* root) {
    if (!root)   return;
    auto dfs = [&](auto&& dfs, TreeNode* root)->TreeNode*
    {
        auto left = root->left, right = root->right;
        TreeNode* last = root;
        root->left = nullptr;
        if (left)
        {
            root->right = left;
            last = dfs(dfs, left);
        }
        if (right)
        {
            last->right = right;
            last = dfs(dfs, right);
        }
        return last;
    };
    dfs(dfs, root);
}